//面试题 03.04. 化栈为队
//实现一个MyQueue类，该类用两个栈来实现一个队列。


// 示例：

// MyQueue queue = new MyQueue();

// queue.push(1);
// queue.push(2);
// queue.peek();  // 返回 1
// queue.pop();   // 返回 1
// queue.empty(); // 返回 false

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//思路：栈混洗的一个特殊例子
#include <stdlib.h>
#include <stdio.h> 
typedef struct Node
{
    int elem;/* data */
    struct Node* last;
    struct Node* next; 
} Node;

typedef struct {
    Node * input_stack ;
    Node * output_stack;

} MyQueue;

void stack_free(Node * stack_buttom);
void change_stack(MyQueue* obj);
Node * get_tail(Node * obj);
Node * create_Node (int x,Node * last, Node *next);
Node * stack_push (Node * obj,int x); 
Node * stack_push_node (Node * *obj,Node* target);
Node * stack_pop (Node ** stack_buttom);

void stack_free(Node * stack_buttom)
{
    while(stack_buttom)
    {
        Node * next = stack_buttom->next;
        free(stack_buttom);
        stack_buttom = next;
    }
}
void change_stack(MyQueue* obj)
{
    if (obj->input_stack !=0)
    {
        Node * new_node = stack_pop(&obj->input_stack);
        while(new_node)
        {
            stack_push_node(&obj->output_stack, new_node);
            new_node = stack_pop(&obj->input_stack);
        }
        
    }
}

Node * get_tail(Node * obj)
{
    if (obj == 0)
    return (Node*)0;
    Node * tail =obj;
    while (tail->next)
    {
        tail =tail->next;
    }
    return tail;
    
}
Node * create_Node (int x,Node * last, Node *next)
{
    Node * new_node = (Node *) malloc(sizeof(Node));
    new_node->elem =x;
    new_node->last =last;
    new_node ->next =next;
    return new_node;
}

// Node * obj 是栈中的一个元素
// x 
Node * stack_push (Node * obj,int x)
{
    Node * tail = get_tail(obj);
    Node * new_node = create_Node(x,tail,0);
    tail->next =  new_node;
    return new_node;
}

Node * stack_push_node (Node * *obj,Node* target)
{
    if (*obj==0)
    {
        *obj = target;
        return target;
    }
    Node * tail = get_tail(*obj);
    tail->next = target;
    target->last = tail;
    return target;
}



Node * stack_pop (Node ** stack_buttom)
{
    Node * tail = get_tail(*stack_buttom);
    if (tail == 0)
        return 0;
    if (tail == *stack_buttom)
    {
        *stack_buttom =0;
        return tail;
    }

    Node * new_tail = tail->last;
    tail ->last = 0;
    tail->next = 0;
    if (new_tail)
        new_tail->next = 0;
    return tail;
}
MyQueue* myQueueCreate() 
{
    MyQueue* myqueue = (MyQueue*)malloc(sizeof(MyQueue));
    myqueue->input_stack=0;
    myqueue->output_stack=0;
    return myqueue;

}

MyQueue* myQueuePush(MyQueue * obj,int x) 
{ // 若定义了input_stack
    if (obj->input_stack)
    {
       stack_push(obj->input_stack,x);
       return obj;
    }
    else
    {
        //第一次push 需要初始化 以下 input_stackinput_stack
        obj->input_stack = (Node *) malloc(sizeof(Node));
        obj->input_stack ->elem =x;
        obj->input_stack ->last = 0;
        obj->input_stack->next = 0;
        return obj;
    }
}


int myQueuePop(MyQueue* obj) 
{
     if(obj->output_stack)
     {
     	Node* new_node=stack_pop(&obj->output_stack); 
        return new_node->elem;

     } 
     else
     {
        change_stack(obj);
        Node* new_node=stack_pop(&obj->output_stack); 
        return new_node->elem;

     }
     
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) 
{

    if(obj->output_stack)
     {
     	Node* new_node=get_tail(obj->output_stack); 
     	
         return new_node->elem;

     } 
     else
     {
         change_stack(obj);
         Node* new_node=get_tail(obj->output_stack); 
     	
         return new_node->elem;
     }

}

/** Returns whether the queue is empty. */
bool  myQueueEmpty(MyQueue* obj) 
{
    if (obj->input_stack ==0 && obj->output_stack ==0)
    {
        return 1;
    }
    
    else
    {
        return 0;
    }   
}


void myQueueFree(MyQueue* obj) {
    stack_free( obj->input_stack);
    stack_free(obj->output_stack);   
}